package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/19 16:50
 * @description <p>排序数组中的两个数字之和</p>
 */

import java.util.ArrayList;
import java.util.List;

/**
 *  题目：输入一个递增排序的数组和一个值 k，请问如何在数组中找出两
 * 个和为 k 的数字并返回它们的下标？假设数组中存在且只存在一对符合条
 * 件的数字，同时一个数字不能使用两次。例如，输入数组[1, 2, 4, 6, 10]，k
 * 的值为 8，数组中的数字 2 与 6 的和为 8，它们的下标分别为 1 与 3。
 */

public class toOffer2_2_6 {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(0, 1);
        arrayList.add(1, 2);
        arrayList.add(2, 4);
        arrayList.add(3, 6);
        arrayList.add(4, 10);

//        for (Integer integer : arrayList) {
//            System.out.println(integer);
//        }

        List<Integer> fun = fun(arrayList, 11);
        System.out.println(fun.get(0));
        System.out.println(fun.get(1));

    }

    public static List<Integer> fun(List<Integer> list, Integer k){

        ArrayList<Integer> backList = new ArrayList<>();

        int slow = 0;
        int fast = list.size() - 1;

        /**
         * 前提条件：数组是有序的
         * 取快慢指针指向的数之和为sum，判断sum大于k，还是小于等于k
         * 如果大于k那说明数大了，需要往小了取，那么fast=fast-1
         * 如果小于k，那么slow+=1
         * 直到sum=k，返回slow和fast的值
         */
        while (slow < fast){
            Integer sum = list.get(slow) + list.get(fast);
            if (sum < k){
                slow ++;
            }
            if (sum > k){
                fast --;
            }
            if (sum.equals(k)){
                backList.add(0, slow);
                backList.add(0, fast);
                return backList;
            }
        }
        return null;
    }
}
